package main

import (
	"fmt"
)

/**
执行用时：92 ms, 在所有 Go 提交中击败了57.86%的用户
内存消耗：2 MB, 在所有 Go 提交中击败了44.52%的用户
 */
var dx = []int{-1, 0, 1, 0}
var dy = []int{0, 1, 0, -1}

func exist(board [][]byte, word string) bool {

	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if dfs(board, word, 0, i, j) {
				return true
			}
		}
	}
	return false
}

func dfs(board [][]byte, word string, u int, x int, y int) bool {

	if board[x][y] != word[u] { return false }
	if u == len(word) - 1 { return true }

	t := board[x][y]
	board[x][y] = '.'
	for i := 0; i < 4; i++ {
		a, b := x + dx[i], y + dy[i]
		if a >= 0 && a < len(board) && b >= 0 && b < len(board[0]) && board[a][b] != '.' {
			if dfs(board, word, u + 1, a, b) { return true }
		}
	}
	board[x][y] = t
	return false
}

func main() {

	board := [][]byte{
		{'A', 'B', 'C', 'E'},
		{'s', 'F', 'C', 's'},
		{'A', 'D', 'E', 'E'},
	}
	fmt.Println(exist(board, "ABCCED"))  // true
}
